package algorithm.leetcode;

/**
 * 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
 * <p>
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 *
 * @author: zhouj-j
 * @since: 2018/7/3
 */
public class __002_add_two_numbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p = l1;

        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        int flag = 0;
        while (l1.next != null && l2.next != null) {
            int v = l1.val + l2.val + flag;
            if (v >= 10) {
                v = v - 10;
                flag = 1;
            } else {
                flag = 0;
            }
            l1.val = v;
            l1 = l1.next;
            l2 = l2.next;
        }

        int v = l1.val + l2.val + flag;
        if (v >= 10) {
            v = v - 10;
            flag = 1;
        } else {
            flag = 0;
        }
        l1.val = v;
        if (l1.next == null) {
            ListNode pre = l2;
            ListNode n = l2.next;
            while (n != null) {
                v = n.val + flag;
                if (v >= 10) {
                    v = v - 10;
                    flag = 1;
                    n.val = v;
                    pre = n;
                    n = n.next;
                } else {
                    flag = 0;
                    n.val = v;
                    break;
                }
            }
            if (flag == 1) {
                pre.next = new ListNode(flag);
            }
            l1.next = l2.next;
        }
        if (l2.next == null) {
            ListNode pre = l1;
            ListNode n = l1.next;
            while (n != null) {
                v = n.val + flag;
                if (v >= 10) {
                    v = v - 10;
                    flag = 1;
                    n.val = v;
                    pre = n;
                    n = n.next;
                } else {
                    flag = 0;
                    n.val = v;
                    break;
                }
            }
            if (flag == 1) {
                pre.next = new ListNode(flag);
            }
        }

        return p;
    }

    public static void main(String[] args) {
        ListNode l2 = new ListNode(1);
        ListNode l1 = new ListNode(9);
        l1.next = new ListNode(8);

        new __002_add_two_numbers().addTwoNumbers(l1, l2);
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
